﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/palindrome-linked-list/
/*
题目描述：
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

 

示例 1：
输入：head = [1,2,2,1]
输出：true

示例 2：
输入：head = [1,2]
输出：false
 

提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
 
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
*/

// 开始解题：
// 方法2——将值复制到数组后用双指针
bool isPalindrome(struct ListNode* head) {
    struct ListNode* cur = head;

    // 先算出链表的长度
    int len = 0;
    while (cur) {
        len++;
        cur = cur->next;
    }

    // 创建数组
    int* temp = (int*)malloc(len * sizeof(int));
    if (NULL == temp) {
        perror("malloc fail");
        exit(-1);
    }

    // 将链表的值复制到数组
    cur = head;
    int i = 0;
    while (cur) {
        temp[i] = cur->val;
        cur = cur->next;
        i++;
    }

    // 使用双指针判断
    int left = 0;
    int right = len - 1;
    while (left < right) {
        if (temp[left] != temp[right]) {
            free(temp);
            temp = NULL;
            return false;
        }
        left++;
        right--;
    }
    free(temp);
    temp = NULL;
    return true;
}
// 时间复杂度：O(n)，n为链表的长度。
// 空间复杂度：O(n)，我们需要额外的n个空间来存储链表节点的值，故空间复杂度为O(n)。